package william.heap;

import william.utils.ArrayUtils;

import java.util.Arrays;

/**
 * @author ZhangShenao
 * @date 2024/2/20
 * @description <a href="https://leetcode.cn/problems/sort-an-array/description/">...</a>
 */
public class Leetcode912_排序数组 {
    public int[] sortArray(int[] nums) {
        //边界条件校验
        if (nums == null || nums.length < 2) {
            return nums;
        }

        //采用堆排序
        heapSort(nums);

        //返回排好序的数组
        return nums;
    }

    /**
     * 堆排序
     */
    private void heapSort(int[] nums) {
        //自底向上,建立大根堆
        buildMaxHeap(nums);

        //初始heapSize = 整个数组长度
        int N = nums.length;
        int heapSize = N;   //初始heapSize为整个数组长度

        //将堆顶元素与N-1位置的元素交换,并将heapSize-1
        swap(nums, 0, N - 1);
        --heapSize;

        //持续该过程,直到heapSize为0
        while (heapSize > 0) {
            shiftDown(nums, heapSize, 0);
            swap(nums, 0, --heapSize);
        }
    }

    /**
     * 构造大根堆
     */
    private void buildMaxHeap(int[] nums) {
        //从叶子节点起,依次进行shiftDown操作
        for (int i = nums.length - 1; i >= 0; i--) {
            shiftDown(nums, nums.length, i);
        }

    }

    /**
     * 下沉操作
     * 针对每个节点,找到其左、右子节点中的最大节点,与其进行交换
     */
    private void shiftDown(int[] nums, int heapSize, int idx) {
        while (idx < heapSize) {
            //找到当前节点的左、右子节点中的最大节点
            int leftIdx = idx * 2 + 1;
            if (leftIdx >= heapSize) {    //无左子节点,终止操作
                break;
            }
            int maxIdx = leftIdx;
            int rightIdx = idx * 2 + 2;
            if (rightIdx < heapSize && nums[rightIdx] > nums[leftIdx]) {
                maxIdx = rightIdx;
            }

            //当前节点比左、右子节点都大,终止操作
            if (nums[idx] >= nums[maxIdx]) {
                break;
            }

            //将当前节点与最大子节点进行交换,并持续该过程
            swap(nums, idx, maxIdx);
            idx = maxIdx;
        }
    }

    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}
